/* 1020. 飞地的数量 */
/**
 * @param {number[][]} grid
 * @return {number}
 */
/* 深度优先搜索 */
var numEnclaves = function (grid) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    const m = grid.length, n = grid[0].length
    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false))

    const dfs = (grid, row, col) => {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return
        }
        visited[row][col] = true

        for (const dir of dirs) {
            dfs(grid, row + dir[0], col + dir[1])
        }
    }

    for (let i = 0; i < m; i++) {
        //遍历边界
        dfs(grid, i, 0)
        dfs(grid, i, n - 1)
    }

    for (let j = 1; j < n - 1; j++) {
        //遍历边界 首尾遍历行的时候已经遍历过了
        dfs(grid, 0, j)
        dfs(grid, m - 1, j)
    }

    let res = 0
    // 找到未访问的即可
    for (let i = 1; i < m - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                res++
            }
        }
    }
    return res
};


/* 广度优先搜索 */
var numEnclaves = function (grid) {
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    const m = grid.length, n = grid[0].length
    const visited = new Array(m).fill(0).map(() => new Array(n).fill(false))
    const queue = []

    for (let i = 0; i < m; i++) {
        if (grid[i][0] === 1) {
            visited[i][0] = true
            queue.push([i, 0])
        }
        if (grid[i][n - 1] === 1) {
            visited[i][n - 1] = true
            queue.push([i, n - 1])
        }
    }

    for (let j = 1; j < n - 1; j++) {
        if (grid[0][j] === 1) {
            visited[0][j] = true
            queue.push([0, j])
        }
        if (grid[m - 1][j] === 1) {
            visited[m - 1][j] = true
            queue.push([m - 1, j])
        }
    }

    while (queue.length) {
        const cell = queue.shift()
        const curRow = cell[0], curCol = cell[1]
        for (const dir of dirs) {
            const nextRow = curRow + dir[0], nextCol = curCol + dir[1]
            if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol] === 1 && !visited[nextRow][nextCol]) {
                visited[nextRow][nextCol] = true
                queue.push([nextRow, nextCol])
            }
        }
    }


    let res = 0
    // 找到未访问的即可
    for (let i = 1; i < m - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                res++
            }
        }
    }
}



const result = numEnclaves([[0, 0, 0, 0], [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]])
console.log("numEnclaves :>>", result);